package com.agile.leetcode.kmp;

import java.util.Arrays;

/**
 * @Author ChenZhangKun
 * @Date 2020/7/31 8:56
 */
public class KMP {
    public static void main(String[] args) {
        String str1="BBC ABCDAB ABCDABCDABDE";
        String str2="ABCDABD";
        int[] ints = kmpNext(str2);
        System.out.println(Arrays.toString(ints));
        int kmp = kmp(str1, str2, ints);
        System.out.println(kmp);
    }

    /**
     * KMP算法
     * @param str1
     * @param str2
     * @param arr
     * @return
     */
    public static int kmp(String str1,String str2,int[] arr){
        int length = str1.length();
        int length1 = str2.length();
        char[] chars = str1.toCharArray();
        char[] chars1 = str2.toCharArray();
        for (int i = 0,j=0; i <length ; i++) {
            while (j>0&&chars[i]!=chars1[j]){
                j=arr[j-1];
            }
            if (chars[i]==chars1[j]){
                j++;
            }
            if (j==length1){
                return i-j+1;
            }
        }
        return -1;
    }
    /**
     * 得到部分匹配表
     * @param str
     * @return
     */
    public static int[] kmpNext(String str){
        // 转成字符数组
        char[] chars = str.toCharArray();
        // 得到长度
        int length = str.length();
        // 创建数组
        int[] arr=new int[length];
        // 初始化第一个元素
        arr[0]=0;
        for (int i = 1,j=0; i <length ; i++) {
            while (j>0&&chars[i]!=chars[j]){
                j=arr[j-1];
            }
            if (chars[i]==chars[j]){
                j++;
            }
            arr[i]=j;
        }
        return arr;
    }
}
